#include <iostream>

using namespace std;

#ifndef max
	#define max( a, b ) ( ((a) > (b)) ? (a) : (b) )
#endif

#ifndef min
	#define min( a, b ) ( ((a) < (b)) ? (a) : (b) )
#endif

int n, W;
int weights[100], values[100];
int V[5][6];

void ReadInput(void) 
{
  n = 5;
  W = 6;
  
  weights[1] = 2, values[1] = 12; 
  weights[2] = 1, values[2] = 10;
  weights[3] = 3, values[3] = 20;
  weights[4] = 2, values[4] = 15;
}

void InitializeMemoryFunctionTable(void)
{
  for(int i=0; i<n+1 ;i++) {
    for(int j=0; j<W+1; j++) {
      if(i == 0 || j==0) {
	V[i][j] = 0;
      } else {
	V[i][j] = -1;
      }
    }
  }
}

int MemoryFunctionKnapsack(int i, int j)
{
  int value = -1;

  if (V[i][j] < 0) {
    if(j < weights[i]) {
      value = MemoryFunctionKnapsack(i-1, j);
    } else {
      value = max(MemoryFunctionKnapsack(i-1, j), values[i] + MemoryFunctionKnapsack(i-1, j-weights[i]));
    }

    V[i][j] = value;
  }

  return V[i][j];
}

int main()
{
  ReadInput();

  InitializeMemoryFunctionTable();
  int maxValue = MemoryFunctionKnapsack(4, 5);

  /* How my table looks? */
  for(int i=0; i<n+1; i++) {
    for(int j=0; j<W+1; j++) {
      cout<<V[i][j]<<" ";
    }
    cout<<endl;
  }

  cout<<"Optimal value is : "<<maxValue<<endl;

  return 0;
}
